/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXB30/FONT#2=BAXI30/FONT#3=SUB/FONT#4=SET1/FONT#5=NGR20/FONT#6=GRK30/FONT#7=SUP/FONT#9=BAXB30/FONT#11=FIX30



␈↓ α∧␈↓␈↓ βα␈↓↓The Post Correspondence Problem as a Question of Ambiguity␈↓







␈↓ α∧␈↓In␈α∂courses␈α∂dealing␈α∂with␈α∂computability␈α∂the␈α∂Post␈α∂Correspondence␈α∂Problem␈α∂(PCP)␈α∞is
␈↓ α∧␈↓usually␈α∩introduced␈α∩by␈α∩definition,␈α∩shown␈α∩to␈α⊃be␈α∩unsolvable␈α∩by␈α∩reducing␈α∩it␈α∩to␈α⊃the
␈↓ α∧␈↓halting␈α∂problem␈α∂(Minsky,␈α∂Manna),␈α∞and␈α∂disposed␈α∂of␈α∂as␈α∞yet␈α∂another␈α∂example␈α∂of␈α∞an
␈↓ α∧␈↓unsolvable␈α
class␈α
of␈α
questions.␈α
 Rarely␈αdo␈α
students␈α
get␈α
any␈α
real␈α
understanding␈αof␈α
what
␈↓ α∧␈↓the␈αPCP␈αis␈αand␈αwhere␈αdifficulties␈αlie␈αin␈αfinding␈αan␈αanswer␈αto␈αa␈αspecific␈αexample.␈α A
␈↓ α∧␈↓partial decision procedure can be very helpful in developing this understanding.

␈↓ α∧␈↓The␈αSardinas-Patterson␈αtest␈αfor␈αambiguity␈αof␈αa␈αcode␈αprovides␈αan␈αalgorithm␈αthat␈αcan
␈↓ α∧␈↓be␈α∞modified␈α∂to␈α∞search␈α∂for␈α∞answers␈α∂to␈α∞any␈α∞specific␈α∂example␈α∞of␈α∂the␈α∞PCP.␈α∂ First,␈α∞we
␈↓ α∧␈↓present␈α
the␈α
Sardinas-Patterson␈αtest.␈α
 Secondly,␈α
we␈α
show␈αhow␈α
the␈α
test␈α
can␈αbe␈α
modified
␈↓ α∧␈↓to␈α
solve␈α
a␈α
problem␈α
similar␈α
but␈α
not␈αequivalent␈α
to␈α
the␈α
PCP.␈α
 We␈α
then␈α
state␈α
the␈αPost
␈↓ α∧␈↓Correspondence␈α
Problem␈α
itself␈α
and␈α
develop␈α
a␈α
partial␈α
decision␈α
procedure␈α
by␈α
a␈α
further
␈↓ α∧␈↓modification␈αto␈αthe␈αalgorithm.⊗↓It␈αis␈α
suggested␈αthat␈αanyone␈αalready␈αfamiliar␈αwith␈α
the
␈↓ α∧␈↓Sardinas-Patterson test skip to section 2.←


␈↓ α∧␈↓␈↓ ∧G␈↓	Section 1: Sardinas Patterson Test␈↓

␈↓ α∧␈↓A␈α
␈↓αcode␈↓␈α
is␈α
a␈α
set␈αof␈α
code␈α
words,␈α
or␈α
strings,␈α
from␈αsome␈α
given␈α
finite␈α
alphabet,␈α
e.g.,␈αfor␈α
the
␈↓ α∧␈↓alphabet␈α{0,␈α1},␈αa␈αsample␈αcode␈αis␈α{001,␈α01,␈α0100,␈α101}.␈α A␈αcode␈αis␈αambiguous␈αif␈αthere
␈↓ α∧␈↓exists␈α∩a␈α∩string␈α∩which␈α∩can␈α∩be␈α∩interpreted,␈α∩or␈α∩parsed,␈α∩in␈α∩two␈α∩different␈α∩ways.␈α∩For
␈↓ α∧␈↓example,␈α∂with␈α∂the␈α∂given␈α∂code,␈α∂the␈α∂string␈α∂"0100101"␈α∂ can␈α∂be␈α∂parsed␈α∂as␈α∂a␈α⊂string␈α∂of
␈↓ α∧␈↓three␈α∂words,␈α∂"01.001.01",␈α∂or␈α∂as␈α∂a␈α∞string␈α∂of␈α∂two␈α∂words,␈α∂"0100.101".␈α∂  The␈α∞Sardinas-
␈↓ α∧␈↓Patterson␈αtest␈αprovides␈αan␈αalgorithm␈αfor␈αdetermining␈αwhether␈αor␈αnot␈αa␈αgiven␈αcode␈αis
␈↓ α∧␈↓ambiguous,␈αand,␈αif␈αit␈αis,␈αthe␈αtest␈αalso␈αprovides␈αthe␈αmeans␈αof␈αconstructing␈αan␈αexample
␈↓ α∧␈↓ambiguous string.

␈↓ α∧␈↓If␈α␈↓εa␈↓=␈↓εbg␈↓,␈αwhere␈α
␈↓εa␈↓,␈α␈↓εb␈↓,␈αand␈α
␈↓εg␈↓␈αare␈αstrings,␈α
then␈α␈↓εb␈↓␈αis␈α
said␈αto␈αbe␈α
a␈α"prefix"␈αof␈α
␈↓εa␈↓␈αand␈α␈↓εg␈↓␈α
is
␈↓ α∧␈↓called␈αthe␈α"tail".␈α If␈αthere␈αexists␈αan␈αambiguous␈αstring,␈αthen␈αit␈αmust␈αbegin␈αwith␈αa␈αcode
␈↓ α∧␈↓word␈α
which␈α
is␈α the␈α
prefix␈α
of␈α
another␈αcode␈α
word.␈α
The␈α
tail␈αmust␈α
then␈α
form␈α
a␈αprefix␈α
of
␈↓ α∧␈↓some␈α∂code␈α∂word.␈α∂ With␈α∂each␈α∂tail␈α∂we␈α⊂keep␈α∂track␈α∂of,␈α∂we␈α∂are␈α∂saying␈α∂that␈α∂there␈α⊂is␈α∂a
␈↓ α∧␈↓string␈αthat␈α
is␈αambiguous␈α
up␈αto␈α
a␈αpoint,␈α
but␈αwe␈α
have␈αthis␈α
overhang,␈αthis␈α
tail,␈αwhich
␈↓ α∧␈↓must still be incorporated as a legal code sequence.

␈↓ α∧␈↓␈↓↓Sardinas-Patterson␈αTest␈↓⊗↓The␈αalgorithm␈α
given␈αwas␈αpresented␈α
by␈αD.␈αHuffman␈αin␈α
an
␈↓ α∧␈↓Information Sciences course at the University of California at Santa Cruz.←:

␈↓ α∧␈↓We make a table, entering the code words in column 0.  We add entries in the rest
␈↓ α∧␈↓of the columns according to the following rules:
␈↓ α∧␈↓     



␈↓ α∧␈↓        1)  to construct column 1, check column 0 to see if any of the code words
␈↓ α∧␈↓        is a prefix of any other code word.
␈↓ α∧␈↓                a)  if there is no such pair of code words, then the code is not
␈↓ α∧␈↓                ambiguous.
␈↓ α∧␈↓                b)  for each such pair that can be found, enter the "tail" in
␈↓ α∧␈↓                column 1, and proceed.
␈↓ α∧␈↓    
␈↓ α∧␈↓        2)  to construct column n+1 (n≥1):
␈↓ α∧␈↓                a)  examine column n for any word13hich is a prefix of some word
␈↓ α∧␈↓                in column 0.  For each such pair, enter the tail in column n+1.
␈↓ α∧␈↓                b) Examine column 0 for any word13hich is a prefix of some word
␈↓ α∧␈↓                in column n.  For each such pair, enter the tail in column n+1.
␈↓ α∧␈↓     
␈↓ α∧␈↓        3)  Continue the process of creating new columns by computing tails until:
␈↓ α∧␈↓                a)  No entries are found for a new column - in this case the code
␈↓ α∧␈↓                is not ambiguous.
␈↓ α∧␈↓                b)  A tail created in some column is one of the original code
␈↓ α∧␈↓                words. In this case the code is ambiguous and an example can be
␈↓ α∧␈↓                constructed from the entries in the table.
␈↓ α∧␈↓                c)  A column is repeated - at this point we know we shall be
␈↓ α∧␈↓                forever repeating the same pattern, as the construction of new
␈↓ α∧␈↓                columns depends only on the single previous column and the
␈↓ α∧␈↓                original code in column 0.  In this case the code is again
␈↓ α∧␈↓                unambiguous.
␈↓ α∧␈↓     

␈↓ α∧␈↓For␈α
example,␈α∞for␈α
the␈α
code␈α∞given␈α
above,␈α
the␈α∞algorithm␈α
yields␈α
the␈α∞table␈α
of␈α∞Figure␈α
1.
␈↓ α∧␈↓The␈α∂ambiguous␈α∂string␈α∂"0100101"␈α∂can␈α∂be␈α∞constructed␈α∂by␈α∂tracing␈α∂the␈α∂history␈α∂of␈α∞the
␈↓ α∧␈↓marked entry. It yields the two parses "01.001.01." and "0100.101.".
␈↓ α∧␈↓                  0      1       2       3
␈↓ α∧␈↓                ______________________________
␈↓ α∧␈↓                001     00       1      01 *** this tail is also a code word!***
␈↓ α∧␈↓                 01
␈↓ α∧␈↓               0100
␈↓ α∧␈↓                101
␈↓ α∧␈↓                                 Figure 1.

␈↓ α∧␈↓ The␈α∂number␈α∂of␈α∂columns␈α∂created␈α∂in␈α∂this␈α∂process␈α∂gives␈α∂an␈α∂indication␈α∂of␈α⊂the␈α∂delay
␈↓ α∧␈↓required,␈α∂in␈α∂the␈α∂worst␈α∂case,␈α∂to␈α∂resolve␈α∂any␈α∂temporary␈α∂ambiguity␈α∂which␈α∂may␈α∞occur
␈↓ α∧␈↓even␈αwhen␈αthe␈α
code␈αitself␈αis␈α
unambiguous.␈α If␈αthe␈α
algorithm␈αstops␈αin␈α
condition␈α3)c),
␈↓ α∧␈↓then␈α
there␈α
is␈α
no␈α
bound␈α
on␈α
this␈α
delay;␈αwe␈α
may␈α
have␈α
to␈α
wait␈α
until␈α
the␈α
entire␈αmessage␈α
is
␈↓ α∧␈↓received before we can start decoding it.


␈↓ α∧␈↓␈↓ ¬ε␈↓	Section 2: Modified PCP␈↓

␈↓ α∧␈↓Suppose␈αwe␈αare␈αgiven␈αa␈αfinite␈αset␈αof␈αordered␈αpairs␈αof␈αstrings␈α{(␈↓εa␈↓β1␈↓,␈↓εb␈↓β1␈↓),␈α...,(␈↓εa␈↓βn␈↓,␈↓εb␈↓βn␈↓)}␈αand



␈↓ α∧␈↓asked␈α
to␈α
determine␈α
whether␈α
or␈α
not␈α
indices␈α
i␈↓β1␈↓,␈α
...,␈α
i␈↓βk␈↓␈α
and␈α
j␈↓β1␈↓,␈α
...,␈α
j␈↓βr␈↓␈α
exist␈α
such␈α
that␈α
␈↓εa␈↓βi␈↓#v1␈↓#␈↓...␈↓εa␈↓βi␈↓#vk␈↓#␈↓
␈↓ α∧␈↓=␈α␈↓εb␈↓βj␈↓#v1␈↓#␈↓...␈↓εb␈↓βj␈↓#vr␈↓#␈↓.␈α That␈αis,␈αwe␈αmust␈αbe␈αable␈αto␈αdecide␈αwhether␈αthere␈αexists␈αa␈αstring␈αthat␈αcan
␈↓ α∧␈↓be␈αinterpreted␈αas␈αconsisting␈αeither␈αentirely␈α
of␈α␈↓εa␈↓'s␈αor␈αentirely␈αof␈α␈↓εb␈↓'s,␈αand␈α
produce␈αthe
␈↓ α∧␈↓string if it does exist.

␈↓ α∧␈↓        This␈α
time␈α
we␈α
make␈α
a␈αtable␈α
with␈α
pairs␈α
of␈α
columns␈αsince␈α
we␈α
need␈α
to␈α
keep␈αthe␈α
␈↓εa␈↓'s
␈↓ α∧␈↓separated␈α
from␈α
the␈α␈↓εb␈↓'s.␈α
 To␈α
get␈αstarted␈α
we␈α
must␈α
find␈αan␈α
␈↓εa␈↓βi␈↓␈α
and␈α␈↓εb␈↓βj␈↓␈α
such␈α
that␈α
one␈αis
␈↓ α∧␈↓the␈α∂prefix␈α∂of␈α∂the␈α∂other.␈α∂ The␈α∂tail␈α∞must␈α∂then␈α∂be␈α∂interpretable␈α∂as␈α∂the␈α∂beginning␈α∞of
␈↓ α∧␈↓either␈α∞a␈α∞string␈α∂of␈α∞␈↓εa␈↓'s␈α∞(if␈α∂␈↓εa␈↓βi␈↓␈α∞was␈α∞the␈α∂prefix␈α∞of␈α∞␈↓εb␈↓βj␈↓)␈α∞or␈α∂a␈α∞string␈α∞of␈α∂␈↓εb␈↓'s␈α∞(if␈α∞␈↓εb␈↓βj␈↓␈α∂was␈α∞the
␈↓ α∧␈↓prefix of ␈↓εa␈↓βi␈↓).

␈↓ α∧␈↓Suppose␈αthat␈αwe␈αhave␈αalready␈αlisted␈αn␈α
columns␈αin␈αthe␈αtable.␈αEach␈αentry␈α␈↓εg␈↓␈αin␈α
column
␈↓ α∧␈↓n␈↓βα␈↓␈α∪indicates␈α∀that␈α∪a␈α∀string␈α∪␈↓εs␈↓␈α∀can␈α∪be␈α∀constructed␈α∪which␈α∀may␈α∪be␈α∀interpreted␈α∪as
␈↓ α∧␈↓consisting␈αentirely␈αof␈α␈↓εb␈↓'s,␈αor␈αentirely␈αof␈α␈↓εa␈↓'s␈αwith␈αthe␈αstring␈α␈↓εg␈↓␈αon␈αthe␈αend.␈αThat␈αis,␈α
the
␈↓ α∧␈↓string␈α
␈↓εs␈↓ = a␈↓β1␈↓...a␈↓βk␈↓a␈↓βk+1␈↓...a␈↓βn␈↓␈α(where␈α
each␈αa␈↓βi␈↓␈α
is␈αa␈α
letter␈αof␈α
the␈αcode␈α
alphabet)␈αis␈α
the␈αsame␈α
as
␈↓ α∧␈↓␈↓εb␈↓βj␈↓#v1␈↓#␈↓...␈↓εb␈↓βj␈↓#vm␈↓#␈↓ for some ␈↓βj␈↓#v1␈↓#␈↓...␈↓βj␈↓#vm␈↓#␈↓, and the same as ␈↓εa␈↓βi␈↓#v1␈↓#␈↓...␈↓εa␈↓βi␈↓#vp␈↓#␈↓εg␈↓ for some ␈↓βi␈↓#v1␈↓#␈↓...␈↓βi␈↓#vp␈↓#␈↓.

␈↓ α∧␈↓ If␈α␈↓εg␈↓␈αitself␈αis␈αan␈α␈↓εa␈↓,␈αthen␈αwe␈αare␈αdone;␈αbut␈αif␈αnot,␈αwe␈αmust␈αcontinue␈αour␈αsearch.␈α If␈α␈↓εg␈↓
␈↓ α∧␈↓is␈α∞a␈α∞prefix␈α∂of␈α∞an␈α∞␈↓εa␈↓βi␈↓,␈α∞then␈α∂we␈α∞extend␈α∞our␈α∂string␈α∞of␈α∞␈↓εa␈↓'s␈α∞by␈α∂that␈α∞␈↓εa␈↓βi␈↓,␈α∞resulting␈α∂in␈α∞the
␈↓ α∧␈↓string␈αwe␈αhad␈αbefore␈αwith␈αthe␈αaddition␈αof␈αthe␈αnew␈αtail␈αon␈αthe␈αend.␈α This␈αstring␈αcan
␈↓ α∧␈↓be␈α∩interpreted␈α⊃as␈α∩consisting␈α∩entirely␈α⊃of␈α∩␈↓εa␈↓'s,␈α∩or␈α⊃entirely␈α∩of␈α∩␈↓εb␈↓'s␈α⊃with␈α∩the␈α∩new␈α⊃tail
␈↓ α∧␈↓appended to the end. Thus, we must add the new tail to the column (n+1)␈↓ββ␈↓.

␈↓ α∧␈↓If␈α
some␈α
␈↓εa␈↓βi␈↓␈α
is␈α
a␈αprefix␈α
of␈α
␈↓εg␈↓,␈α
then␈α
we␈αhave␈α
extended␈α
our␈α
␈↓εa␈↓-interpretation␈α
of␈α
␈↓εs␈↓,␈αand
␈↓ α∧␈↓the␈α
new␈α
tail␈α
is␈α
the␈α
"leftover"␈α
in␈α
the␈α
same␈α
sense␈α
that␈α
␈↓εg␈↓␈α
was.␈α
 Thus␈α
we␈α
add␈α
the␈αnew
␈↓ α∧␈↓tail to column (n+1)␈↓βα␈↓.

␈↓ α∧␈↓We␈α∂do␈α⊂an␈α∂analogous␈α∂examination␈α⊂of␈α∂column␈α∂n␈↓ββ␈↓.␈α⊂ If␈α∂we␈α∂ever␈α⊂find␈α∂an␈α∂␈↓εa␈↓βi␈↓␈α⊂in␈α∂some
␈↓ α∧␈↓column␈α∞n␈↓βα␈↓,␈α
or␈α∞a␈α
␈↓εb␈↓βj␈↓␈α∞in␈α
some␈α∞column␈α∞n␈↓ββ␈↓,␈α
then␈α∞we␈α
are␈α∞through.␈α
 There␈α∞is␈α∞a␈α
solution
␈↓ α∧␈↓string␈αand␈αit␈αcan␈αbe␈αconstructed␈αby␈αtracing␈αthe␈αhistory␈αof␈αthe␈αentry␈α␈↓εa␈↓βi␈↓␈αin␈αn␈↓βα␈↓,␈αor␈α␈↓εb␈↓βj␈↓␈αin
␈↓ α∧␈↓n␈↓ββ␈↓, as the case may be.

␈↓ α∧␈↓This discussion is summarized as the following algorithm:
␈↓ α∧␈↓    
␈↓ α∧␈↓        1)  Enter the ␈↓εa␈↓'s and ␈↓εb␈↓'s in columns 0␈↓βα␈↓ and 0␈↓ββ␈↓, respectively.
␈↓ α∧␈↓     
␈↓ α∧␈↓        2)  Create columns 1␈↓βα␈↓ and 1␈↓ββ␈↓ :
␈↓ α∧␈↓                a)  If any ␈↓εa␈↓βi␈↓ is a prefix of any ␈↓εb␈↓βj␈↓, enter the tail in 1␈↓βα␈↓.
␈↓ α∧␈↓                b)  If any ␈↓εb␈↓βi␈↓ is a prefix of any ␈↓εa␈↓βj␈↓, enter the tail in 1␈↓ββ␈↓.
␈↓ α∧␈↓    
␈↓ α∧␈↓        3)  To create columns (n+1)␈↓βα␈↓ and (n+1)␈↓ββ␈↓ :
␈↓ α∧␈↓                a1)  If any string in n␈↓βα␈↓ is a prefix of any ␈↓εa␈↓βi␈↓,
␈↓ α∧␈↓                enter the tail in (n+1)␈↓ββ␈↓.
␈↓ α∧␈↓                a2)  If any ␈↓εa␈↓βi␈↓ is a prefix of any string in n␈↓βα␈↓,
␈↓ α∧␈↓                enter the tail in (n+1)␈↓βα␈↓.



␈↓ α∧␈↓                b1)  If any string in n␈↓ββ␈↓ is a prefix of any ␈↓εb␈↓βi␈↓,
␈↓ α∧␈↓                enter the tail in (n+1)␈↓βα␈↓.
␈↓ α∧␈↓                b2)  If any ␈↓εb␈↓βi␈↓ is a prefix of any string in n␈↓ββ␈↓,
␈↓ α∧␈↓                enter the tail in (n+1)␈↓ββ␈↓.
␈↓ α∧␈↓    
␈↓ α∧␈↓        4)  Continue creating new columns according to step 3) until one of the
␈↓ α∧␈↓          following conditions occurs:
␈↓ α∧␈↓                a)  The process closes out, that is, the entries in n␈↓βα␈↓ and n␈↓ββ␈↓
␈↓ α∧␈↓                  are such that the columns (n+1)␈↓βα␈↓ and (n+1)␈↓ββ␈↓ are empty.  In
␈↓ α∧␈↓                  this case we can say that no solution is possible.
␈↓ α∧␈↓                b)  Some column n␈↓βα␈↓ contains an ␈↓εa␈↓βi␈↓, or some column n␈↓ββ␈↓ contains
␈↓ α∧␈↓                  a ␈↓εb␈↓βi␈↓; then a solution exists and can be found by tracing the
␈↓ α∧␈↓                  history of such an entry through the table.
␈↓ α∧␈↓                c)  A pattern of columns develops which will continue infinitely,
␈↓ α∧␈↓                  that is, an ␈↓εa␈↓-␈↓εb␈↓ pair of columns is repeated; then there is no
␈↓ α∧␈↓                  solution. New columns depend only on the single previous pair of
␈↓ α∧␈↓                  columns and the original columns 0␈↓βα␈↓ and 0␈↓ββ␈↓. Therefore
␈↓ α∧␈↓                  once any n␈↓βα␈↓-n␈↓ββ␈↓ pair of columns is repeated, the same
␈↓ α∧␈↓                  columns will follow the pair ad infinitum.


␈↓ α∧␈↓     One␈α⊃of␈α⊃the␈α⊃conditions␈α⊂4)a)␈α⊃-␈α⊃4)c)␈α⊃is␈α⊂guaranteed␈α⊃to␈α⊃occur.␈α⊃ Since␈α⊃"tails"␈α⊂have
␈↓ α∧␈↓length␈α∞less␈α∞than␈α∞some␈α∞code,␈α∞and␈α∞there␈α∞is␈α∞a␈α∞maximum␈α∞length␈α∞among␈α∞the␈α∞␈↓εa␈↓βi␈↓␈α∞and␈α
␈↓εb␈↓βi␈↓,
␈↓ α∧␈↓there␈α∃is␈α∃a␈α∃maximum␈α∃tail␈α∃length,␈α⊗and␈α∃thus␈α∃a␈α∃finite␈α∃number␈α∃of␈α⊗possible␈α∃tails.
␈↓ α∧␈↓Therefore, only a finite number of n␈↓βα␈↓-n␈↓ββ␈↓ column pairs is possible.
␈↓ α∧␈↓␈↓ ∧≡␈↓	Section 3: Post Correspondence Problem␈↓

␈↓ α∧␈↓    The␈α
difference␈α
between␈α
the␈α∞problem␈α
stated␈α
above␈α
and␈α
the␈α∞Post␈α
Correspondence
␈↓ α∧␈↓Problem␈αis␈αthat␈αwe␈αwere␈αnot␈αrestricted␈αto␈αusing␈αthe␈αsame␈αindexing␈αsequence␈αfor␈α
both
␈↓ α∧␈↓␈↓εa␈↓'s and ␈↓εb␈↓'s. The following statement of the PCP is taken from Minsky.

␈↓ α∧␈↓␈↓ β$␈↓↓Post Correspondence Problem:␈↓

␈↓ α∧␈↓␈↓ β$Given␈αan␈αalphabet␈αA␈αand␈αa␈αfinite␈αset␈αof␈αpairs␈αof␈αwords␈α(␈↓εa␈↓βi␈↓,
␈↓ α∧␈↓␈↓ β$␈↓εb␈↓βi␈↓)␈α⊂in␈α⊂the␈α⊂alphabet␈α∂A,␈α⊂is␈α⊂there␈α⊂a␈α∂sequence␈α⊂i␈↓β1␈↓,␈α⊂i␈↓β2␈↓,␈α⊂...,␈α⊂i␈↓βn␈↓␈α∂of
␈↓ α∧␈↓␈↓ β$selections such that the strings
␈↓ α∧␈↓␈↓ ¬␈↓εa␈↓βi␈↓#v1␈↓#␈↓εa␈↓βi␈↓#v2␈↓#␈↓...␈↓εa␈↓βi␈↓#vn␈↓#␈↓ and ␈↓εb␈↓βi␈↓#v1␈↓#␈↓εb␈↓βi␈↓#v2␈↓#␈↓...␈↓εb␈↓βi␈↓#vn␈↓#␈↓

␈↓ α∧␈↓␈↓ β$formed␈α#by␈α"concatenating--writing␈α#down␈α#in␈α"order--
␈↓ α∧␈↓␈↓ β$corresponding ␈↓εa␈↓'s and ␈↓εb␈↓'s are identical?

␈↓ α∧␈↓We␈αcan␈αmodify␈α
the␈αtable␈αbuilding␈α
procedure␈αfurther␈αto␈αsearch␈α
for␈αa␈αsolution␈α
to␈αthe
␈↓ α∧␈↓PCP,␈αproviding␈αa␈αpartial␈αdecision␈αprocedure.␈α If␈αa␈αsolution␈αexists,␈αthen␈αwe␈αwill␈αfind
␈↓ α∧␈↓it,␈α
but␈α
if␈α
there␈α
is␈α
no␈α
solution␈α
we␈α
may␈α
end␈α
up␈α
looking␈α
forever␈α
as␈α
we␈α
lose␈α
the␈α
guarantee
␈↓ α∧␈↓of␈α∂termination␈α∂provided␈α∂by␈α∂the␈α∂algorithm␈α∂above.␈α∂ As␈α∂an␈α∂example,␈α∂we␈α∂construct␈α∂a
␈↓ α∧␈↓solution for the set of pairs {(1,111), (10111,10), (10,0)} in Figure 2.



␈↓ α∧␈↓We␈α
again␈α
build␈αa␈α
table␈α
with␈α
column␈αpairs.␈α
 This␈α
time,␈α
to␈αget␈α
started␈α
we␈α
must␈αfind␈α
an
␈↓ α∧␈↓␈↓εa␈↓βi␈↓␈α⊂and␈α⊂␈↓εb␈↓βi␈↓␈α⊂(with␈α⊂the␈α⊂␈↓αsame␈↓␈α⊂index)␈α⊂such␈α⊂that␈α⊂one␈α⊂is␈α⊂a␈α⊂prefix␈α⊂of␈α⊂the␈α⊂other.␈α⊃ As␈α⊂we
␈↓ α∧␈↓continue␈α∂listing␈α∂columns,␈α∂we␈α∞must␈α∂be␈α∂careful␈α∂to␈α∞ensure␈α∂that␈α∂we␈α∂are␈α∂constructing␈α∞a
␈↓ α∧␈↓string␈αinterpretable␈αas␈αa␈αsequence␈αof␈α␈↓εa␈↓βi␈↓'s␈αand␈αalso␈αas␈αthe␈α␈↓αsame␈αsequence␈↓␈αof␈α␈↓εb␈↓βi␈↓'s.␈αEvery
␈↓ α∧␈↓time we make use of an ␈↓εa␈↓βi␈↓ we must also be able to use the corresponding ␈↓εb␈↓βi␈↓.
␈↓ α∧␈↓        1)  Enter the ␈↓εa␈↓'s and ␈↓εb␈↓'s in columns 0␈↓βα␈↓ and 0␈↓ββ␈↓, respectively, being
␈↓ α∧␈↓          careful to enter them in order.
␈↓ α∧␈↓    
␈↓ α∧␈↓        2)  Create columns 1␈↓βα␈↓ and 1␈↓ββ␈↓:
␈↓ α∧␈↓                a)  If any ␈↓εa␈↓βi␈↓ is a prefix of ␈↓εb␈↓βi␈↓ (note the same index is required),
␈↓ α∧␈↓                  then enter the tail in 1␈↓βα␈↓.
␈↓ α∧␈↓                b)  If any ␈↓εb␈↓βi␈↓ is a prefix of the corresponding ␈↓εa␈↓βi␈↓, then enter the
␈↓ α∧␈↓                  tail in 1␈↓ββ␈↓.
␈↓ α∧␈↓     
␈↓ α∧␈↓        3)  Create columns (n+1)␈↓βα␈↓ and (n+1)␈↓ββ␈↓:
␈↓ α∧␈↓                a1)  If any string in n␈↓βα␈↓ is an ␈↓εa␈↓βi␈↓, write the corresponding ␈↓εb␈↓βi␈↓ in
␈↓ α∧␈↓                   column (n+1)␈↓βα␈↓.
␈↓ α∧␈↓                a2)  If any string in n␈↓βα␈↓ is a prefix of any ␈↓εa␈↓βi␈↓, check the tail:
␈↓ α∧␈↓                          i)  If the tail is the corresponding ␈↓εb␈↓βi␈↓, then we have
␈↓ α∧␈↓                            a solution!
␈↓ α∧␈↓                         ii)  If the tail is a prefix of the corresponding ␈↓εb␈↓βi␈↓,
␈↓ α∧␈↓                            enter the ␈↓αnew␈↓ tail (i.e., what is left of ␈↓εb␈↓βi␈↓ after
␈↓ α∧␈↓                            deleting the tail from the front of it) in (n+1)␈↓βα␈↓.
␈↓ α∧␈↓                        iii)  If the corresponding ␈↓εb␈↓βi␈↓ is a prefix of the tail,
␈↓ α∧␈↓                            enter the new tail in (n+1)␈↓ββ␈↓.
␈↓ α∧␈↓                a3)  If any ␈↓εa␈↓βi␈↓ is a prefix of any string in n␈↓βα␈↓, add the corre-
␈↓ α∧␈↓                   sponding ␈↓εb␈↓βi␈↓ to the end of the tail, and enter the whole thing
␈↓ α∧␈↓                   in column (n+1)␈↓βα␈↓. (e.g. In Figure 2, the entry "1111" in column
␈↓ α∧␈↓                   2␈↓βα␈↓, results from "1", in 0␈↓βα␈↓, being a prefix of "11", in 1␈↓βα␈↓,
␈↓ α∧␈↓                   thus "111", ␈↓εb␈↓β1␈↓, was added to the tail "1". Again, in 3␈↓βα␈↓,
␈↓ α∧␈↓                   "1", in 0␈↓βα␈↓, is a prefix of "1111", in 2␈↓βα␈↓, so "111", ␈↓εb␈↓β1␈↓,
␈↓ α∧␈↓                   is added to the tail, producing the entry "111111".)
␈↓ α∧␈↓    
␈↓ α∧␈↓                b1)  If any string in n␈↓ββ␈↓ is an ␈↓εb␈↓βi␈↓, write the corresponding ␈↓εa␈↓βi␈↓ in
␈↓ α∧␈↓                   column (n+1)␈↓ββ␈↓. (e.g. In column 1␈↓ββ␈↓, "111" appears, thus "1",
␈↓ α∧␈↓                   the corresponding ␈↓εa␈↓βi␈↓, appears in 2␈↓ββ␈↓.)
␈↓ α∧␈↓                b2)  If any string in n␈↓ββ␈↓ is a prefix of any ␈↓εb␈↓βi␈↓, check the tail:
␈↓ α∧␈↓                          i)  If the tail is the corresponding ␈↓εa␈↓βi␈↓, then we have
␈↓ α∧␈↓                            a solution!
␈↓ α∧␈↓                         ii)  If the tail is a prefix of the corresponding ␈↓εa␈↓βi␈↓,
␈↓ α∧␈↓                            enter the ␈↓αnew␈↓ tail in (n+1)␈↓ββ␈↓.
␈↓ α∧␈↓                        iii)  If the corresponding ␈↓εa␈↓βi␈↓ is a prefix of the tail,
␈↓ α∧␈↓                            enter the new tail in (n+1)␈↓βα␈↓. (e.g. In Figure 2,
␈↓ α∧␈↓                            column 2␈↓ββ␈↓ contains "1", which is a prefix of ␈↓εb␈↓β1␈↓;
␈↓ α∧␈↓                            the tail is "11"; the corresponding ␈↓εa␈↓β1␈↓ is "1",
␈↓ α∧␈↓                            which is a prefix of the tail "11", thus the ␈↓αnew␈↓
␈↓ α∧␈↓                            tail is "1" and is entered in 3␈↓βα␈↓.)
␈↓ α∧␈↓                b3)  If any ␈↓εb␈↓βi␈↓ is a prefix of any string in n␈↓ββ␈↓, add the corre-



␈↓ α∧␈↓                   sponding ␈↓εa␈↓βi␈↓ to the end of the tail, and enter the whole thing
␈↓ α∧␈↓                   in column (n+1)␈↓ββ␈↓.
␈↓ α∧␈↓    

␈↓ α∧␈↓ To␈α∞facilitate␈α∞the␈α∞construction␈α∞of␈α∞our␈α
solution␈α∞we␈α∞subscript␈α∞each␈α∞entry␈α∞in␈α∞the␈α
table
␈↓ α∧␈↓with␈α∂the␈α∂index␈α∂of␈α∂the␈α⊂pair␈α∂used␈α∂in␈α∂deriving␈α∂it.␈α⊂ We␈α∂also␈α∂use␈α∂arrows␈α∂to␈α⊂trace␈α∂the
␈↓ α∧␈↓history␈α⊂of␈α∂entries.␈α⊂Then,␈α⊂when␈α∂we've␈α⊂found␈α∂that␈α⊂a␈α⊂solution␈α∂exists,␈α⊂we␈α⊂can␈α∂simply
␈↓ α∧␈↓follow␈α
the␈α
path␈α
from␈α
the␈α
first␈α
column␈α
pair,␈α
noting␈α
the␈α
subscripts␈α
as␈α
we␈α
go,␈α
and␈αwe
␈↓ α∧␈↓are␈αleft␈α
with␈αthe␈α
desired␈αlist␈α
of␈αindices.␈α
If␈αa␈α
solution␈αexists,␈α
it␈αmust␈α
be␈αconstructable
␈↓ α∧␈↓by the given rules.
␈↓ α∧␈↓    
␈↓ α∧␈↓        0␈↓βα␈↓    0␈↓ββ␈↓        1␈↓βα␈↓    1␈↓ββ␈↓       2␈↓βα␈↓      2␈↓ββ␈↓      3␈↓βα␈↓      3␈↓ββ␈↓      4␈↓βα␈↓    4␈↓ββ␈↓
␈↓ α∧␈↓     ___________________________________________________________________
␈↓ α∧␈↓    
␈↓ α∧␈↓         1     111      11␈↓β(1)␈↓          1111␈↓β(1)␈↓      111111␈↓β(1)␈↓
␈↓ α∧␈↓     10111     10             111␈↓β(2)␈↓          1␈↓β(1)␈↓      1␈↓β(1)␈↓         111␈↓β(1)␈↓
␈↓ α∧␈↓        10       0                                                          *␈↓β(3)␈↓
␈↓ α∧␈↓    

␈↓ α∧␈↓                                        Figure 2.
␈↓ α∧␈↓    

␈↓ α∧␈↓When␈α
a␈α
solution␈α
does␈α
not␈α
exist,␈α
we␈α
may␈α
or␈α
may␈α
not␈α
be␈α
able␈α
to␈α
determine␈α∞so.␈α
 The
␈↓ α∧␈↓table␈αmight␈α"close␈αout"␈αafter␈αa␈αfinite␈αnumber␈αof␈αsteps,␈αthat␈αis,␈αthere␈αmay␈αbe␈αno␈αmore
␈↓ α∧␈↓possible␈α∞entries.␈α∞ In␈α∞this␈α∞case␈α∂there␈α∞is␈α∞no␈α∞solution.␈α∞ The␈α∞column␈α∂generating␈α∞process
␈↓ α∧␈↓might␈α∩also␈α∩continue␈α∩ad␈α∩infinitum;␈α∩this␈α∩is␈α∩detectable␈α∩in␈α∩special␈α∩cases␈α∩but␈α∪not␈α∩in
␈↓ α∧␈↓general. For example, if any column-pair is ever repeated, there is no solution.

␈↓ α∧␈↓The␈α∞difficulties␈α∂arise␈α∞in␈α∞step␈α∂3)␈α∞parts␈α∞a3)␈α∂and␈α∞b3).␈α∞ The␈α∂entries␈α∞afforded␈α∂by␈α∞these
␈↓ α∧␈↓rules,␈αand␈αthus␈α
the␈αtails␈αused␈α
elsewhere,␈αcan␈αgrow␈α
arbitrarily␈αlong,␈αthus␈α
ruining␈αour
␈↓ α∧␈↓chances for a guarantee of termination of the process.

␈↓ α∧␈↓Of␈α⊂course,␈α⊂we␈α⊂have␈α⊃not␈α⊂shown␈α⊂that␈α⊂the␈α⊃problem␈α⊂is␈α⊂unsolvable.␈α⊂ The␈α⊃motive␈α⊂for
␈↓ α∧␈↓introducing␈α∞a␈α∂partial␈α∞decision␈α∂procedure␈α∞is␈α∞to␈α∂offer␈α∞students␈α∂some␈α∞insight␈α∂into␈α∞the
␈↓ α∧␈↓problem␈α∩itself.␈α∩ The␈α⊃proof␈α∩of␈α∩unsolvability␈α⊃may␈α∩then␈α∩be␈α⊃presented␈α∩as␈α∩usual,␈α⊃by
␈↓ α∧␈↓reduction␈α⊂to␈α⊂the␈α⊂Halting␈α∂Problem␈α⊂or␈α⊂some␈α⊂other␈α∂class␈α⊂of␈α⊂problems␈α⊂known␈α⊂to␈α∂the
␈↓ α∧␈↓students.
␈↓ α∧␈↓␈↓ ¬c␈↓	References␈↓






␈↓ α∧␈↓Huffman, D., IS10:Introduction to Cybernetics, Information Sciences Board,
␈↓ α∧␈↓        University of California at Santa Cruz, Spring Quarter, 1978.
␈↓ α∧␈↓     
␈↓ α∧␈↓Manna, Z., ␈↓αMathematical Theory of Computation␈↓, McGraw-Hill, New York,



␈↓ α∧␈↓        New York, 1974.
␈↓ α∧␈↓                                                                           
␈↓ α∧␈↓Minsky, M., ␈↓αComputation: Finite and Infinite Machines␈↓, Prentice-Hall, Inc.,
␈↓ α∧␈↓        Englewood Cliffs, New Jersey, 1967.